import java.util.ArrayList;
import java.util.Arrays;

//四数之和，使得四个数的和为target的值，四数之和简化为三数之和
public class sumOfFourNumber {//那如果我将其中的一个数据删除之后，那不就转化为三数之和了？感觉可以
    public ArrayList sum(ArrayList list,int target,int[] nums){
        Arrays.sort(nums);//排序
        for (int j=0;j<nums.length;j++){

            if(nums[j]>target && nums[j]>=0){//剪枝处理，大于零时，且大于target时，肯定不可能能凑齐target，但是小于0时，且大于target时，可能能够凑出target
                break;
            }

            if(j>0&&nums[j]==nums[j-1]){//对nums元素进行去重
                continue;
            }

            for (int i=j+1;i<nums.length;i++){//三数之和

                if ((nums[j]+nums[i]>target) && (nums[j]+nums[i]>=0)){//二次剪枝处理，和第一次剪枝的理由相同
                    break;
                }

                if(i>j+1&&nums[i]==nums[i-1]){//对nums元素进行去重
                    continue;
                }

                int left = i+1;
                int right = nums.length-1;
                while (left<right){
                    if (nums[j]+nums[i]+nums[left]+nums[right]>target) right--;
                    else if (nums[j]+nums[i]+nums[left]+nums[right]<target) left++;
                    else {
                        list.add(new int[]{nums[j],nums[i],nums[left],nums[right]});
                        while ( left<right && nums[right] == nums[right - 1]) right--;
                        while (left<right && nums[left] == nums[left + 1]) left++;
                        right--;
                        left++;
                    }
                }
            }

        }
        return list;
    }



    public static void main(String[] args) {
        ArrayList<int[]> list = new ArrayList<>();//用于存放最后的四元组
        var main = new sumOfFourNumber();
        int[] nums = {1, 0, -1, 0, -2, 2};
        main.sum(list,0,nums);
        for (int[] l:list){
            System.out.println(Arrays.toString(l));
        }
    }
}
